package com.fe.class03;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description 反转单链表
 * @Author sosuke :-)
 * @Date 2021/12/5 18:16
 */
public class Code01_ReverseLinkedList {

    public static class Node<T> {
        T data;
        Node<T> next = null;

        public Node(T data) {
            this.data = data;
        }
    }

    /**
     * 使用两个指针完成单链表的反转
     * pre、head、next，三个指针是这个顺序，顺着单链表依次往后移动，直到head == null
     * next移动--->（head指针反转）---> pre移动--->head移动
     *
     * @return 返回反转后的头节点
     */
    public static Node<Integer> reverseLinkedList(Node<Integer> head) {
        Node<Integer> pre = null;
        Node<Integer> next = null;
        while (head != null) {
            next = head.next; // next移动
            head.next = pre; // 反转
            pre = head; // pre移动
            head = next; // head移动，移动后，下次要再判断head是否为null
        }
        return pre;
    }

    public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 10;
        int maxValue = 100;
        for (int i = 0; i < testTime; i++) {
            // 原地反转单链表
            Node<Integer> head = generateRandomLinkedList(maxSize, maxValue);
            List<Node<Integer>> originLinkedList = getOriginLinkedList(head);
            Node<Integer> reverseHead = reverseLinkedList(head); // 反转后，原head.next = null
            Node<Integer> head2 = testReverseLinkedList(originLinkedList);
            if(!nodeEqual(reverseHead, head2)) {
                System.out.println("Fuck!");
                System.out.print("head1===>");
                printLinkedList(reverseHead);
                System.out.print("head2===>");
                printLinkedList(head2);
                return;
            }
        }
        System.out.println("Nice!");
        Node<Integer> head = generateRandomLinkedList(maxSize, maxValue);
        System.out.print(" origin===>");
        printLinkedList(head);
        Node<Integer> reverseHead = reverseLinkedList(head);
        System.out.print("reverse===>");
        printLinkedList(reverseHead);
    }

    /**
     * 判断两个单链表是否相等
     * @param head1
     * @param head2
     * @return
     */
    public static boolean nodeEqual(Node<Integer> head1, Node<Integer> head2) {
        Node<Integer> p1 = head1;
        Node<Integer> p2 = head2;
        while (p1 != null && p2 != null) {
            if (!p1.data.equals(p2.data)) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1 == null && p2 == null;
    }

    /**
     * 使用list容器实现
     * @param list
     * @return
     */
    public static Node<Integer> testReverseLinkedList(List<Node<Integer>> list) {
        if (null == list || list.size() == 0) return null;
        // 反转
        list.get(0).next = null;
        for (int i = 1; i < list.size(); i++) {
            list.get(i).next = list.get(i - 1);
        }
        // 返回反转后的头节点
        return list.get(list.size() - 1);
    }

    /**
     * 把链表按顺序添加到容器中
     *
     * @param head
     * @return
     */
    public static List<Node<Integer>> getOriginLinkedList(Node<Integer> head) {
        List<Node<Integer>> list = new ArrayList<>();
        for (; head != null; head = head.next) {
            list.add(head);
        }
        return list;
    }

    /**
     * 随机生成单链表
     *
     * @return
     */
    public static Node<Integer> generateRandomLinkedList(int maxSize, int maxValue) {
        // [0,maxSize]
        int size = (int) (Math.random() * (maxSize + 1));
        if (size == 0) return null;
        Node<Integer> head = new Node<>((int) (Math.random() * (maxValue + 1)));
        size--;
        Node<Integer> pre = head;
        for (int i = 0; i < size; i++) {
            Node<Integer> next = new Node<>((int) (Math.random() * (maxValue + 1)));
            pre.next = next;
            pre = next;
        }
        return head;
    }

    /**
     * 打印单链表
     *
     * @param head
     */
    public static void printLinkedList(Node<Integer> head) {
        if (null == head) {
            System.out.println("\"null\"");
            return;
        }
        Node<Integer> cur = head;
        while (null != cur) {
            System.out.print(cur.data + "--->");
            System.out.print(cur.next == null ? "null" : "");
            cur = cur.next;
        }
        System.out.println();
    }
}
